package DFS;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @Author ChanZany
 * @Date 2021/5/18 12:41
 * @Version 1.0
 */
public class permutations2 {
    //打印所有可能的输出结果
    private static void dfs(List<List<Integer>> res, List<Integer> cur, int[] arr, int[] visit,HashSet<List<Integer>> set) {
        if (cur.size()==arr.length) {
            if (set.contains(cur)) return;
            set.add(cur);
            res.add(new ArrayList<>(cur));//注意创建新的对象，否则cur随方法进行发生改变
            return;
        }
        for(int i=0;i<arr.length;i++){
            if(visit[i]==0){
                //探索
                visit[i]=1;
                cur.add(arr[i]);
                dfs(res,cur,arr,visit,set);
                //回溯
                visit[i]=0;
                cur.remove(cur.size()-1);
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 2};
//        int[] visit = new int[arr.length];
        List<List<Integer>> res = new ArrayList<>();
        dfs(res,new ArrayList<Integer>(),arr,new int[arr.length],new HashSet<List<Integer>>());
        res.forEach(System.out::println);
    }
}
